package main

type Node struct {
	val   int
	next  *Node
	prev2 *Node
	next2 *Node
}

type MaxQueue struct {
	head  *Node
	tail  *Node
	head2 *Node // head is max
	tail2 *Node
}

func Constructor() MaxQueue {
	q := MaxQueue{
		head:  &Node{},
		head2: &Node{},
		tail2: &Node{},
	}
	q.tail = q.head
	q.head2.next2 = q.tail2
	q.tail2.prev2 = q.head2
	return q
}

func (this *MaxQueue) Max_value() int {
	if this.head.next == nil {
		return -1
	}
	return this.head2.next2.val
}

func (this *MaxQueue) Push_back(value int) {
	node := &Node{
		val: value,
	}
	// normal queue
	this.tail.next = node
	this.tail = node
	// ordered queue
	pivot := this.head2 // the last one greater than value
	for pivot != nil {
		if pivot.next2 == nil {
			// value is min
			node.prev2 = pivot
			node.next2 = pivot.next2
			pivot.next2.prev2 = node
			pivot.next2 = node
			break
		}
		if pivot.next2.val < value {
			node.prev2 = pivot
			node.next2 = pivot.next2
			pivot.next2.prev2 = node
			pivot.next2 = node
			break
		}
		pivot = pivot.next2
	}
}

func (this *MaxQueue) Pop_front() int {
	if this.head.next == nil {
		return -1
	}
	node := this.head.next
	// normal queue
	this.head.next = this.head.next.next
	if node.next == nil { // node is tail
		this.tail = this.head
	}
	// ordered queue
	node.prev2.next2 = node.next2
	node.next2.prev2 = node.prev2
	node.next2 = nil
	node.prev2 = nil
	return node.val
}

func main() {
	q := Constructor()
	println(q.Pop_front())
	println(q.Max_value())
}
